package org.example.sort;
//堆排序算法思想
//基本原理
//堆结构：利用堆这种数据结构的特性进行排序，堆是一个完全二叉树
//堆的性质：
//大顶堆：父节点的值大于或等于其子节点的值
//小顶堆：父节点的值小于或等于其子节点的值
//排序过程：
//构建堆：将待排序数组构建成一个大顶堆
//交换元素：将堆顶元素（最大值）与末尾元素交换
//重新调整：重新调整剩余元素为大顶堆
//重复执行：重复步骤2-3，直到排序完成
//核心特点
//不稳定排序：相等元素的相对位置可能会改变
//原地排序：只需要常数级别的额外空间
//时间复杂度稳定：无论最好、最坏、平均情况都是O(n log n)
//基于比较：属于比较排序算法
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9, 1, 3, 7};
        System.out.println("排序前:");
        printArray(arr);
        heapSort(arr);
        System.out.println("排序后:");
        printArray(arr);
    }
    /**
     * 堆排序主方法
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // 1. 构建大顶堆
        // 从最后一个非叶子节点开始，从下往上，从右往左调整
        for (int i = n / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, n);
        }
        // 2. 调整堆结构+交换堆顶元素与末尾元素
        for (int j = n - 1; j > 0; j--) {
            // 将堆顶元素与末尾元素进行交换
            swap(arr, 0, j);
            // 重新对堆进行调整
            adjustHeap(arr, 0, j);
        }
    }
    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr 待调整的数组
     * @param i 非叶子节点在数组中的索引
     * @param length 对多少个元素进行调整
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i]; // 先取出当前元素i
        // 开始调整
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { // k从i的左子节点开始
            // 如果左子节点小于右子节点，k指向右子节点
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            // 如果子节点大于父节点，将子节点赋给父节点（不用进行交换）
            if (arr[k] > temp) {
                arr[i] = arr[k];
                i = k; // 继续向下调整
            } else {
                break;
            }
        }
        arr[i] = temp; // 将temp值放到最终的位置
    }
    /**
     * 交换元素
     * @param arr 数组
     * @param a 索引a
     * @param b 索引b
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    /**
     * 打印数组
     * @param arr 数组
     */
    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if (i != arr.length - 1) {
                System.out.print(arr[i] + ",");
            } else {
                System.out.print(arr[i]);
            }
        }
        System.out.println();
    }
}
